Search for: All records

{"Abstract":["In the modular robot reconfiguration problem, we are given $$n$$ cube-shaped modules (or robots) as well as two configurations, i.e., placements of the $$n$$ modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves", in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times.\n\n\nFor many years it has been known that certain module configurations in this model require at least $$\\Omega(n^2)$ moves to reconfigure between them, and works for any dimension $$d\\ge 3$$. In this paper, we introduce the first universal reconfiguration algorithm—i.e., we show that any $$n$$-module configuration can reconfigure itself into any specified $$n$$-module configuration using just sliding moves. Our algorithm achieves reconfiguration in $O(n^2)$ moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration."]} 

We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward. 

We introduce basic, but heretofore generally unexplored, problems in computational origami that are similar in style to classic problems from discrete and computational geometry. We consider the problems of folding each corner of a polygon P to a point p and folding each edge of a polygon P onto a line segment L that connects two boundary points of P and compute the number of edges of the polygon containing p or L limited by crease lines and boundary edges. 

Imagine t ≤ mn unit-square tiles in an m×n rectangular box that you can tilt to cause all tiles to slide maximally in one of the four orthogonal directions. Given two tiles of interest, is there a tilt sequence that brings them to adjacent squares? We give a linear-time algorithm for this problem, motivated by 2048 endgames. We also bound the number of reachable configurations, and design instances where all t tiles permute according to a cyclic permutation every four tilts. 

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k, s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s , each of which induces a connected subgraph (when s=0 , the k parts are perfectly balanced, and we call it k-BCP for short). A recombination is an operation that takes a (k, s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0 , we wish to determine whether there exists a sequence of recombinations that transform A into B via (k, s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k , and (3) we provide negative instances for s≤n/(3k) . (4) We show that the problem is PSPACE-complete when k∈O(nε) and s∈O(n1−ε) , for any constant 0<ε≤1 , even for restricted settings such as when G is an edge-maximal planar graph or when k≥3 and G is planar.